class Solution {
    long res = 0;
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length+1;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g,i->new ArrayList<>());
        for(int[] e:roads){
            int a = e[0];
            int b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs(0,g,seats,-1);
        return res;
    }
    public long dfs(int node,List<Integer>[] g,int seats,int parent)
    {
        long size = 1;
        long cnt = 0;
        for(int val : g[node])
        {
            if(val!=parent)
            {
              cnt = dfs(val,g,seats,node);
              size+=cnt;
              res+=(cnt+seats-1)/seats;
            }
        }
        return size;
    }
}
